The present invention relates to data communications devices and more specifically to network devices which implement protocols to operate on data in a data communications system.
In digital communications systems, data is routinely transmitted between many processing devices over a network. For example, in computer networks such as the Internet, data is typically sent from one computer to another through network communications devices such as modems, hubs, routers, bridges, switches and/or other computers interconnected by transmission media or data links. The data itself is stored and communicated as a series of binary digits (bits) represented by zeros and ones. During data communications, the manner in which the bits of data are specifically arranged and the order in which they are exchanged between devices is called a protocol. Protocols are usually established by industry standards. There are many different types of protocols serving different purposes, but each typically involves a sending device that arranges data in one manner, and a receiving device that detects the specific arrangement of the data in order to make use of the data upon reception.
For example, blocks of data can be reduced in size by compression protocols before transmission from a sending computer in order to conserve bandwidth. When privacy is desired, data can be altered by encryption protocols into a state that makes the data unreadable by anyone or any device not authorized to read the data. The data can travel across the network in an encrypted and compressed state until it reaches its destination. Upon receipt, the receiving computer decrypts (i.e. decodes) and decompresses the data according to these protocols into a form useable by an intended application.
In some data communications devices, the main central processing unit (CPU) of the device is responsible for performing protocols on data, such as the compression, decompression and encryption, decryption protocols noted above. In this case, the protocols are performed completely under software control by a program stored in memory. In other devices, separate dedicated hardware processors are provided to perform individual protocols. In hardware implementations, the CPU of the device merely schedules the flow of data through the device, and at the appropriate time, instructs each separate dedicated processor to perform a single respective protocol for which that dedicated processor is designed.
For instance, in a modem, as data is received from the sending application it is buffered in memory before transmission onto a computer network. The CPU in the modem assembles the data into a packet, and then compresses that packet of data. After compression, if privacy is desired, the CPU then encrypts the data packet. When the CPU has completed its task, the packet is processed further and transmitted from the modem.
An example of one type of compression/decompression protocol is called V.42bis. To compress data, V.42bis creates a dictionary of commonly occurring strings of bits in data. For a string that commonly occurs, the dictionary specifies a short replacement string which, when transmitted, takes up less space, and therefore saves network bandwidth. Compressed data according to V.42bis is stored in a data structure called a xe2x80x9ctriexe2x80x9d. Tries are a species of multi-way search trees, designed to represent sets of character strings. To decompress data stored in a trie, a complex series of trie traversals are required to reconstruct the original data. Prior art systems perform these trie traversals in either software or with a dedicated hardware processor, as explained above.
Other protocols exist that are used to format data during data communications in order for devices to communicate effectively and efficiently. For instance, during assembly of data packets, signaling information must be provided along with the actual message data in the packets for communications to take place. Various signaling protocols have been developed to support uniform communication of data packets.
One such widely used protocol is the High Level Data Link Control (xe2x80x9cHDLCxe2x80x9d) protocol, as defined in Level 2 of the Open Systems Interconnection (xe2x80x9cOSIxe2x80x9d) model. HDLC is a bit-oriented protocol for sending packets between devices. HDLC requires the sender to distinguish the start and end of a packet from the actual data portion of the packet. To do so, HDLC uses a flag to indicate the start and end of packets. The flag consists of a zero bit followed by six one bits and ends with a zero bit, and appears as 01111110. In HDLC, a process called xe2x80x9czero stuffingxe2x80x9d can be used to distinguish the flag portion of a packet from the data portion (which may itself contain an embedded series of ones that could be mistaken for a flag). In zero stuffing, a zero bit xe2x80x9c0xe2x80x9d is inserted into packet data being transmitted if five continuous one bits xe2x80x9c11111xe2x80x9d are detected. Thus, zero stuffing converts xe2x80x9c11111xe2x80x9d into xe2x80x9c111110xe2x80x9d in the data portion of a packet, in order to distinguish the data from the beginning and end of the packet. The receiver of the xe2x80x9cstuffedxe2x80x9d data packet then xe2x80x9cunstuffsxe2x80x9d the data by removing any zero bit following five continuous one bits (i.e., 111110 becomes 11111).
Other protocols called SLIP (xe2x80x9cSerial Line Internet Protocolxe2x80x9d) and PPP (xe2x80x9cPoint-To-Pointxe2x80x9d) are communications protocols that allow computers to simulate a direct connection to the Internet. SLIP/PPP uses special control characters that need to be detected and/or replaced in the data stream. Creation and insertion as well as detection and replacement of the control characters in prior art SLIP/PPP protocol systems is typically done with a dedicated hardware circuit processing each packet transmitted and received.
Another process occurring in data communications is called the Cyclic Redundancy Check (xe2x80x9cCRCxe2x80x9d). CRC is the most common method of error detection for most data communications. A CRC value is computed for a packet, attached to that packet during transmission, and upon receipt of that packet the receiver can verify the correctness of the contents of the packet by re-calculating the CRC value using the packet data and comparing the result to the attached CRC. As with the aforementioned protocols, prior art CRC computation is performed either in dedicated hardware circuitry or in software using the CPU of the device.
Currently available data communication devices that implement protocols such as compression/decompression, encryption/decryption and so forth suffer a variety of problems. Software implementations lack execution speed due to the large number of processing cycles required when executing protocols on the CPU. A CPU executing a program to compress and encrypt data must process data fast enough to fully utilize available data communications bandwidth. Fast processors are expensive and increase the cost of data communications devices. Software implementations of protocols also require a software engineer to xe2x80x9cdesignxe2x80x9d code for the protocol, which can be an error prone task.
For example, current hardware implementations of protocols are very inflexible. If the protocol changes due to evolving standards, a new chip must be created making old devices obsolete. The inflexibility of hardware solutions leads to problems when defacto protocol standards evolve that are inconsistent with a current hardware implementation. Additionally, hardware implementations may restrict future improvements in devices containing the dedicated processors because the hardware inflexibility may no longer interface to the changing functionality of the device.
The present invention overcomes the problems associated with software and hardware protocol implementations in prior art data communications devices. For simplicity herein, a data communications device that performs a protocol is called a network device. The present invention provides a network device including a unique co-processor having a symmetrical architecture and an extended processor instruction set to provide instructions allowing protocols to operate more efficiently. The network device including the co-processor off-loads the complex protocol processing tasks from the CPU in the network device.
According to one aspect of the invention, a network device used for processing data communications is provided. The network device comprises at least one input interface receiving data and at least one output interface for transmitting data. Since more than one interface may be provided, the device can handle multiple streams of data. The network device further includes memory for storing data and a system bus coupled to the input interface, the output interface, and the memory. Also coupled to the system bus is a central processing unit (CPU) which controls the receipt of data by the input interface and stores the data in memory. The network device also includes a co-processor coupled to the system bus which has at least one internal programmable processor programmed to execute multiple protocols. By executing multiple protocols in the co-processor, the CPU is free to perform other network device tasks, such as routing, for example.
In the network device, the coprocessor handles retrieving the data from the memory upon an indication from the central processing unit. Then the co-processor performs each of the multiple protocols on the data for which the co-processor is programmed. Finally, the co-processor returns the data to the memory for transmission from the output interface of the network device. In this manner, the co-processor can be programmed to perform many protocols on the same data within the co-processor. This reduces the amount of transfers of the data between the main memory and CPU of the network device.
By off-loading protocol operation to the co-processor in the network device, faster data throughput rates may be achieved. One reason for this is that the co-processor can be programmed. Programmability allows the co-processor to perform multiple protocols at once, either independently of each other, or in conjunction with each other. Since only one programmed co-processor can implement multiple protocols, the system bus and CPU of the network device are free from much of the associated protocol processing.
According to-another aspect of the invention, a programmable multiple-protocol co-processor apparatus for use in a data communications device is provided. Such a coprocessor embodiment may be an ASIC, for example, which resides on the system bus of the network device embodiment noted above.
According to this embodiment of the invention, the co-processor includes at least one programmable processor and at least one memory system coupled to the programmable processor. An interface is coupled to the memory system and to the programmable processor. The interface can accept at least one protocol program downloaded into the memory system from a host computer processor. The host computer can be, for example, the network device noted above. The programmable processor executes the protocol program that is downloaded. If there is more than one processor executing more than one protocol program, the co-processor can execute multiple protocols. Alternatively, if one processor exists and is supplied with multiple protocol programs, the co-processor can also execute multiple protocols. The programmable aspect of the co-processors allows it to change according to changing protocols by being re-programmed.
In another embodiment, the invention provides a multi-processor embodiment of the co-processor which can quickly process data according to the program(s) which were downloaded. According to this embodiment, first and second programmable processors are coupled to respective first and second local memory systems. A bus system is coupled to the first and second programmable processors and the first and second local memory systems. The bus system has an interface capable of being connected to a host system for transferring data between the host system and the first and second programmable processors and the first and second local memory systems.
Since the co-processor is programmable and has at least one internal programmable processor, it can implement a variety of different algorithms simultaneously on many streams of data passing through the network device. The programmable nature of the co-processor also allows protocols to be easily changed by being reprogrammed if protocol standards evolve. Programmability of dual processors in the co-processor also allows flexibility in intended operation. The co-processor can thus implement multiple protocols independently of each other, or in conjunction with each other.
Specifically, according to other embodiments of the invention, the first and second programmable processors are each programmed to execute at least one protocol. Examples of protocols which may be executed are encryption, decryption, compression, decompression, HDLC framing, point-to-point protocol, serial line interface protocol, MNP5-Microcom network protocol, V.42bis. Other known data communications protocols may be programmed and implemented by the processors as needed.
The co-processor embodiments noted above rely on at least one processor to perform execution of each protocol program. That is, the co-processor contains separate individual processors therein, aside from its memory and interface systems.
These first and second programmable processors each include an extended instruction set allowing the processors to be programmed with instructions to concurrently execute multiple protocols independent of each other and allowing the processors to be programmed with instructions to concurrently execute multiple protocols in conjunction with each other.
According to another aspect of this invention, each processor circuit which serves as the first and second processor in the co-processor is itself novel. As such, the invention provides embodiments directed to a processor including an input interface for loading communications programs and communications data as well as a first unit including processor instruction logic circuits for executing first portions of the communications programs. The first unit generally corresponds to a set of instructions provided with the processor from the manufacturer of the processor.
The invention however extends this instruction set and provides, in the processor, a second unit including extension processor instruction logic circuits for executing second portions of the communications programs and for processing at least one portion of the communications data. The second unit corresponds to an extension arithmetic logic unit (XALU) created according to this invention. The second portions of the communication programs are the extension ALU instructions which can, according to this invention, operate on the data passing through the processor. The processor also includes an output interface for storing results of the processing. The extension instructions are provided in addition to an existing core instruction set in each processor within the co-processor.
According to other embodiments of this invention, the extension instructions provide various operations. More specifically, according to this invention, a zero stuffing instruction logic circuit includes an input logic device which accepts an input bit stream. A detecting logic device detects a predetermined sequence of bits. An insertion logic device inserts a modifier into the input bit stream thus creating a modified bit stream and an overflow bit stream. Finally, an output logic device stores the modified bit stream in a predefined location and stores the overflow bit stream in a second predefined location and maintains overflow state information. By providing this circuitry, the invention offers a zero stuffing instruction for a microprocessor, such as a RISC microprocessor.
According to another embodiment of the invention, a zero unstuffing instruction logic circuit is provided and includes an input logic device which accepts an input bit stream and a detecting logic device which detects a first predetermined sequence of bits. A removal logic device is included which removes a second predetermined sequence from the input bit stream creating a modified bit stream. An output logic device is included which stores the modified bit stream in a predefined location and maintains borrow state and error state information. By providing this circuitry, the invention provides a zero unstuffing operation in the form of a single microprocessor instruction.
In yet another embodiment of the invention, a partial subtraction and conditional move instruction logic circuit, for use in rightward trie traversal, is provided. The circuit including an input logic device which accepts a first input data, a second input data and a third input data. A comparing logic device is included which performs a comparison between the first input data and the third input data. If the comparison results in the first input data being equal to the third input data then a down traversal state is set, and if the comparison results in the first input data being greater than the third input data then the second input data is copied into a predefined location and no state is set. If the comparison results in the first input data being less than the third input data then an insertion state is set and the first input data is inserted into a trie data structure. An output logic device stores the third input state in a predefined location and stores the first input data into the trie data structure and maintains the down traversal state and the insertion state information.
In yet another embodiment of the invention, a partial compare and conditional move instruction logic circuit, for upward trie traversal, is provided. The circuit includes an input logic device which accepts a first input data and a second input data. Also included is a comparing logic device which performs a comparison between the first input data and the second input data. If the comparison results in the first input data being equal to the second data then a terminate traversal state is set. If the comparison results in the first input data being not equal to the second data then the first input data is copied to a predefined location and no state is set. An output logic device stores the first input state in a predefined location and maintains the terminate traversal state information.
In yet another embodiment of the invention, a multiple compare instruction logic circuit is provided including an input logic device which accepts a first input data, a second input data and a third input data. A comparing logic device performs a comparison between the first input data and a series of predefined characters in the third input data. If the comparison results in the first input data being equal to any character in the series of predefined characters then a character match state is set. A comparing logic device performs a comparison between the first input data and a predefined boundary. If the first input data is within the predefined boundary then a character boundary state is set. An output logic device maintains the character match state and the character boundary state information.
In yet another embodiment of the invention, a CRC instruction logic circuit is provided including an input logic device which accepts a first input data, a second input data and a third input data. A calculating logic device which computes a CRC value based upon the polynomial defined in the first input data, the current state of the CRC calculation stored in the second input data and a third input data containing a portion of a message upon which to calculate a CRC. An output logic device which stores the CRC value in a predefined location.
Having these operations available as instructions which may be called by programs that implement the various protocols is beneficial for many reasons. Since the actual operations of each instruction are not performed purely in software, but rather as circuitry which carries out the instruction when called, higher co-processor operation speeds result. Also, since the instruction circuitry is activated by calling the instruction, the program can control when the circuitry is used, thus avoiding unnecessary operation of the circuitry as in prior art hardware only implementations. That is, extension instructions offering the aforementioned functions only activate their associated circuitry when called. This allows the processors to concentrate on program execution and conserves processor cycles.
The present invention utilizes the extensible instruction set feature of a programmable processor to implement time consuming data communications techniques as the aforementioned instruction circuits in hardware. These instructions overcome the aforementioned prior art problems of software and hardware solutions.